	//封装哈希表类
    function HashTable() {
        //属性
        this.storage = []
        this.count = 0//计算已经存储的元素个数
        //装填因子：loadFactor > 0.75时需要扩容；loadFactor < 0.25时需要减少容量
        this.limit = 7//初始长度
  
        //方法
        //哈希函数
        HashTable.prototype.hashFunc = function(str, size){
        //1.定义hashCode变量
        let hashCode = 0
  
        //2.霍纳法则，计算hashCode的值
        //cats -> Unicode编码
        for(let i = 0 ;i < str.length; i++){
          // str.charCodeAt(i)//获取某个字符对应的unicode编码
          hashCode = 37 * hashCode + str.charCodeAt(i)
        }
  
        //3.取余操作
        let index = hashCode % size
        return index
      }
  
      //一.插入&修改操作
      HashTable.prototype.put = function (key, value){
        //1.根据key获取对应的index
        let index = this.hashFunc(key, this.limit)
  
        //2.根据index取出对应的bucket
        let bucket = this.storage[index]
  
        //3.判断该bucket是否为null
        if (bucket == null) {
          bucket = []
          this.storage[index] = bucket
        }
  
        //4.判断是否是修改数据
        for (let i = 0; i < bucket.length; i++) {
          let tuple = bucket[i];
          if (tuple[0] == key) {
            tuple[1] = value
            return//不用返回值
          }
        }
  
        //5.进行添加操作
        bucket.push([key, value])
        this.count += 1
  
        //6.判断是否需要扩容操作
        if(this.count > this.limit * 0.75){
          let newSize = this.limit * 2
          let newPrime = this.getPrime(newSize)
          this.resize(newPrime)
        }
      }
  
      //二.获取操作
      HashTable.prototype.get = function(key){
        //1.根据key获取对应的index
        let index = this.hashFunc(key, this.limit)
  
        //2.根据index获取对应的bucket
        let bucket = this.storage[index]
  
        //3.判断bucket是否等于null
        if (bucket == null) {
          return null
        }
  
        //4.有bucket，那么就进行线性查找
        for (let i = 0; i < bucket.length; i++) {
          let tuple = bucket[i];
          if (tuple[0] == key) {//tuple[0]存储key，tuple[1]存储value
            return tuple[1]
          }
        }
  
        //5.依然没有找到，那么返回null
        return null
      }
  
      //三.删除操作
      HashTable.prototype.remove = function(key){
        //1.根据key获取对应的index
        let index = this.hashFunc(key, this.limit)
  
        //2.根据index获取对应的bucket
        let bucket = this.storage[index]
  
        //3.判断bucket是否为null
        if (bucket == null) {
          return null
        }
  
        //4.有bucket,那么就进行线性查找并删除
        for (let i = 0; i < bucket.length; i++) {
          let tuple = bucket[i]
          if (tuple[0] == key) {
            bucket.splice(i,1)
            this.count -= 1 
            return tuple[1]
  
            //6.缩小容量
            if (this.limit > 7 && this.count < this.limit * 0.25) {
              let newSize = Math.floor(this.limit / 2)
              let newPrime = this.getPrime(newSize)
              this.resize(newPrime)
            }
          }
      }
  
        //5.依然没有找到，返回null
        return null
      }
  
    /*------------------其他方法--------------------*/
    //判断哈希表是否为null
    HashTable.prototype.isEmpty = function(){
      return this.count == 0
    }
  
    //获取哈希表中元素的个数
    HashTable.prototype.size = function(){
      return this.count
    }
  
  
    //哈希表扩容
    HashTable.prototype.resize = function(newLimit){
      //1.保存旧的storage数组内容
      let oldStorage = this.storage
  
      //2.重置所有的属性
      this.storage = []
      this.count = 0
      this.limit = newLimit
  
      //3.遍历oldStorage中所有的bucket
      for (let i = 0; i < oldStorage.length; i++) {
        //3.1.取出对应的bucket
        const bucket = oldStorage[i];
  
        //3.2.判断bucket是否为null
        if (bucket == null) {
          continue
        }      
  
        //3.3.bucket中有数据，就取出数据重新插入
        for (let j = 0; j < bucket.length; j++) {
          const tuple = bucket[j];
          this.put(tuple[0], tuple[1])//插入数据的key和value
        }
      }
    }
  
    //判断传入的num是否质数
    HashTable.prototype.isPrime = function(num){
        if (num <= 1) {
          return false
        }
        //1.获取num的平方根:Math.sqrt(num)
        //2.循环判断
        for(var i = 2; i<= Math.sqrt(num); i++ ){
          if(num % i == 0){
            return false;
          }
        }
          return true;
      }
  
      //获取质数的方法
      HashTable.prototype.getPrime = function(num){
         //7*2=14,+1=15,+1=16,+1=17(质数)
        while (!this.isPrime(num)) {
          num++
        }
        return num
      }
   }
  